1. Field of the Invention
This invention relates to computer systems and, more specifically, to race resolution mechanisms for use by computer systems.
2. Background Information
A computer system typically comprises one or more processors linked to a main memory by a bus or other interconnect. In most computer systems, main memory organizes the instructions and data being stored into units typically referred to as “blocks”, each of which is separately addressable and may be of a fixed size. Instructions and data are typically moved about the computer system in terms of one or more blocks.
Ordinarily, a processor will retrieve data, e.g., one or more blocks, from main memory, perform some operation on it, and eventually return the results back to main memory. Retrieving data from main memory and providing it to a processor can take significant time especially in terms of the high operating speeds of processors. To reduce such latencies as well as to reduce the number of times a processor must access main memory, modern processors and/or processor chipsets include one or more cache memories or caches. A cache is a small, fast memory module that is placed in close proximity to the processor. Many caches are static random access memories (SRAMs), which are faster, but more expensive, than dynamic random access memories (DRAMs), which are often used for main memory. The cache is used to store information, e.g., data or instructions, which the processor is currently using or is likely to use in the near future. There are two basic types of caches: “write-through” caches and “write-back” caches.
With a write-through cache, whenever a processor modifies or updates a piece of data in the processor's cache, main memory's copy of that data is automatically updated. This is accomplished by having the processor write the data back to memory whenever the data is modified or updated. A write-back cache, in contrast, does not automatically send modified or updated data to main memory. Instead, the updated data remains in the cache until some more convenient time, e.g., when the processor is idle, at which point the modified data is written back to memory. The utilization of write-back caches typically improves system performance. In some systems, a write-back or victim buffer is provided in addition to the cache. “Victim data” refers to modified data that is being removed from the processor's cache in order to make room for new data received at the processor. Typically, the data selected for removal from the cache is data the processor is no longer using. The victim buffer stores this modified data which is waiting to be written back to main memory.
Symmetrical Multiprocessor (SMP) Systems
Multiprocessor computing systems, such as symmetrical multiprocessor (SMP) systems, provide a computer environment in which software applications may run on a plurality of processors using a single address space or shared memory abstraction. In a shared memory system, each processor can access any data item without a programmer having to worry about where the data is or how to obtain its value. This frees the programmer to focus on program development rather than on managing partitioned data sets and communicating values.
Cache Coherency
Because more than one processor of the SMP system may request a copy of the same memory block from main memory, cache coherency protocols have been developed to ensure that no processor relies on a memory block that has become stale, typically due to a modification or update performed to the block by some other processor. Many cache coherency protocols associate a state with each cache line. A given memory block, for example, may be in a shared state in which copies of the block may be present in the caches associated with multiple processors. When a memory block is in the shared state, a processor may read from, but not write to, the respective block. To support write operations, a memory block may be in an exclusive state. In this case, the block is owned by a single processor which may write to the cache line. When the processor updates or modifies the block, its copy becomes the most up-to-date version, while corresponding copies of the block at main memory and/or other processor caches become stale.
When a processor wishes to obtain exclusive ownership over a memory block that is currently in the shared state (i.e., copies of the block are present in the caches of other processors) invalidate requests are typically issued to those other processors. When an invalidate request is received by a given processor, its cache is searched for the specified memory block. If the block is found, it is transitioned to an invalid state. Many caches assign or associate a valid bit with each memory block or cache line stored in the cache. If the bit is asserted, then the cache line is considered to be valid and may be accessed and utilized by the processor. When a memory block is initially received from main memory, the valid bit is asserted and the memory block is stored in the cache. When an invalidate request is received, the valid bit of the respective cache line is de-asserted, thereby indicating that the cache line is no longer valid.
There are two classes of cache coherency protocols: snooping and directory based. With snooping, the caches monitor or snoop all transactions traversing the shared memory bus, looking for transactions that reference a memory block stored at the cache. If such a transaction is detected, the cache updates the status information for its copy of the memory block based on the snoop transaction. In this way, every cache that has a copy of a given memory block also has a copy of the status information of that block. With a directory based protocol, the state of each block is kept in a single, centralized location in the system, called a directory. Status information is not maintained in the individual caches.
FIG. 1 is a highly schematic illustration of a prior art directory 100. Directory 100 has a plurality of entries 102a-d each of which corresponds to a respective memory block. The directory 100 is organized, moreover, such that each entry 102a-d has a plurality of fields or cells for storing state and/or status information for the respective block. In particular, the directory 100 has an address column 103 that stores the address of the memory block, an owner column 104 that stores the identity of the entity, e.g., a processor or main memory itself, that is considered to be the owner of the memory block, and a sharer column 106 that stores the identity of those processors or other system entities that have a shared copy of the block.
The sharer column 106 may have a plurality of sub-columns 106a-c, each of which may contain the identity of a particular processor that has a shared copy of the respective memory block. If a request for shared access to a memory block is received from a first processor, P1, main memory examines the directory entry, e.g., entry 102c, for the block to determine its owner. As memory is itself the owner of the block, memory sends its copy of the block to P1 and enters P1's identifier (ID) into one of the sharer fields, e.g. field 106b, of the respective directory entry, e.g., entry 102c, thereby noting that P1 has a shared copy of the block. Since P1 only requested shared access to the memory block, the contents of the entry's owner field 104 are not modified.
If P1 issues a request for exclusive or write access to some other memory block, e.g., the block corresponding to entry 102d, main memory again examines the contents of entry 102d. Suppose that, at the time the request is received, the owner field reflected that memory was the owner of the memory block as shown in parentheses. In this case, memory sends the block to P1, and replaces the contents of the owner field 104 with P1's ID to reflect that P1, rather than memory, is now the owner of the memory block. P1 may then modify or update the memory block. If a request from a second processor, e.g., processor P2, is subsequently received for a shared copy of this memory block, main memory examines entry 102d of the directory 100 and determines that P1 is the owner of the memory block. Because its copy of the block, i.e., the copy stored at main memory, may be stale, memory does not forward its copy to P2. Instead, memory may be configured to forward the request to P1 and add P2's ID to one of the sharer fields, e.g., field 106a. In response to the forwarded request, P1 may then supply P2 with a copy of the modified memory block from P1's cache. Alternatively, main memory may be configured to force P1 to relinquish ownership of the memory block and return the modified version to memory so that memory can send a copy of the up-to-date version to P2.
Several approaches have also been developed for handling multiple, concurrent requests to the same block. For example, suppose the directory 100 receives a first request for exclusive access to a memory block followed by a request for shared access to the memory block. Suppose further that after receiving the request for shared access, the directory 100 receives a second request for exclusive access to the same block. If the second request is received before the first request completes, i.e., before the first requester receives the memory block and before all necessary acknowledgements have been sent and received, then the two requests are considered to be concurrent. A first approach to resolving concurrent requests for the same memory block accepts the first request, e.g., the first request for exclusive access, but turns away any further requests, e.g., the request for shared access and the second request for exclusive access, until the first request completes, i.e., until the first requester acknowledges receipt of the block. Specifically, the directory 100 ignores all of the later requests and instructs the subsequent requesters to retry their requests. Although this approach is relatively easy to implement at the directory, it requires the incorporation of starvation-avoidance logic to prevent a requester from constantly being turned away each time it retries its request.
Another approach calls for the directory 100 to build a queue containing all of the concurrent requests for the memory block. When the first requester acknowledges completion of its request, the directory pops the next request, i.e., the second request, from the head of the queue and processes it. The directory also advances the remaining requests in the queue. When the second requester acknowledges completion of its request, the directory pops the next, i.e., third, request from the head of the queue and processes. This process is repeated until all requests buffered in the queue have been processed. Although this approach has worked well for small computer systems, it does not scale well to computer systems having large numbers, e.g., tens or hundreds, of processors and/or other requesting entities, such as input/output (I/O) devices. For example, to avoid any retries, the directory would need a queue of sufficient depth to accommodate concurrent requests from all system entities. Such a requirement can become especially disadvantageous when the system has multiple directories.
Accordingly, a need exists for a system the can efficiently handle multiple, concurrent requests to the same memory block and that also scales well to very large computer systems.